package top.minuy.structure.graph.cc.dfs;

import top.minuy.structure.graph.representations.table.Graph;

/**
 * 联通分量
 * Connected Component
 *
 * @author Minuy
 * @time 17:11
 * @date 2021/11/160
 */
public class CCV1 {
    private Graph g;
    private boolean[] isVisited;

    private int CCCount = 0;

    public CCV1(Graph g) {
        this.g = g;

        if (g.isDirected()){
            throw new IllegalArgumentException("CC only works in undirected graph.");
        }

        this.isVisited = new boolean[g.V()];

        // 遍历所有联通分量
        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                // 新的联通分量
                CCCount++;

                order(v);
            }
        }
    }

    private void order(int v) {
        isVisited[v] = true;
        for (Integer w : g.adj(v)) {
            if (!isVisited[w]) {
                order(w);
            }
        }
    }

    /**
     * 获取联通分量
     *
     * @return int 整个图的联通分量
     * @author Minuy
     * @date 2021/11/16 17:13
     */
    public int count() {
        return CCCount;
    }
}